// 题目描述
// 528. 按权重随机选择
// 难度
// 中等
// 298
// 给你一个 下标从 0 开始 的正整数数组 w ，其中 w[i] 代表第 i 个下标的权重。
// 请你实现一个函数 pickIndex ，它可以 随机地 从范围 [0, w.length - 1] 内（含 0 和 w.length - 1）选出并返回一个下标。选取下标 i 的 概率 为 w[i] / sum(w) 。
// 例如，对于 w = [1, 3]，挑选下标 0 的概率为 1 / (1 + 3) = 0.25 （即，25%），而选取下标 1 的概率为 3 / (1 + 3) = 0.75（即，75%）。
//   示例 1：
// 输入：
// ["Solution","pickIndex"]
// [[[1]],[]]
// 输出：
// [null,0]
// 解释：
// Solution solution = new Solution([1]);
// solution.pickIndex(); // 返回 0，因为数组中只有一个元素，所以唯一的选择是返回下标 0。
// 示例 2：
// 输入：
// ["Solution","pickIndex","pickIndex","pickIndex","pickIndex","pickIndex"]
// [[[1,3]],[],[],[],[],[]]
// 输出：
// [null,1,1,1,1,0]
// 解释：
// Solution solution = new Solution([1, 3]);
// solution.pickIndex(); // 返回 1，返回下标 1，返回该下标概率为 3/4 。
// solution.pickIndex(); // 返回 1
// solution.pickIndex(); // 返回 1
// solution.pickIndex(); // 返回 1
// solution.pickIndex(); // 返回 0，返回下标 0，返回该下标概率为 1/4 。
//
// 由于这是一个随机问题，允许多个答案，因此下列输出都可以被认为是正确的:
// [null,1,1,1,1,0]
// [null,1,1,1,1,1]
// [null,1,1,1,0,0]
// [null,1,1,1,0,1]
// [null,1,0,1,0,0]
// ......
// 诸若此类。
//   提示：
// 1 <= w.length <= 104
// 1 <= w[i] <= 105
// pickIndex 将被调用不超过 104 次
// 通过次数57,842提交次数119,487
// https://leetcode.cn/problems/random-pick-with-weight/

// 这道题目可以当成模板记下来，当给你权重数组时
// 1. 通过构造前缀和数组
// 2. 产生随机数 target
// 3. 二分搜索定位到 target 的索引（-1）
/**
 * @param {number[]} w 权重数组
 */
var Solution = function (w) {
  const preSum = new Array(w.length + 1).fill(0)
  for (let i = 1; i <= w.length; i++) {
    preSum[i] = preSum[i - 1] + w[i - 1]
  }

  this.preSum = preSum
  this.total = preSum[preSum.length - 1]
}

/**
 * @return {number}
 */
Solution.prototype.pickIndex = function () {
  const target = Math.floor(Math.random() * this.total) + 1

  // 用二分搜索算法寻找大于等于这个随机数的最小元素索引
  let left = 0
  let right = this.preSum.length - 1

  // 这里有个细节需要注意，当找到这个最小元素的索引时
  // 其实它是前缀和数组的最小索引，与原数组的索引有一位偏移
  // 所以结果应该 -1
  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2)
    const cur = this.preSum[mid]
    if (cur > target) {
      // 寻找第一个比 target 大的数字
      right = mid - 1
    } else if (cur === target) {
      // 寻找到 target 返回索引 - 1
      return mid - 1
    } else if (cur < target) {
      left = mid + 1
    }
  }

  return left - 1
}


const map = new Map()
var obj = new Solution([1, 3])
for (let i = 0; i < 400; i++) {
  const key = obj.pickIndex()
  map.set(key, (map.get(key) || 0) + 1)
}

console.log(map.entries())
